Bà sinh ngày 27 tháng 8 năm 1963 tại Hà Nội.

Nguyên quán của bà tại thôn Phượng Vũ, xã Phượng Dực, huyện Phú Xuyên, tỉnh Hà Đông (nay thuộc Hà Nội)[3]. Song thân của bà đều là những du học sinh tại Liên Xô. Tên của bà được giải thích bao gồm Nguyễn (họ cha) Phương (tên mẹ) và Nga (nơi cha mẹ bà gặp nhau).[4]

Mẹ của bà từng nhiều năm công tác tại Đại sứ quán Việt Nam tại Liên Xô. Điều này có ảnh hưởng khá lớn đến sự nghiệp ngoại giao của bà sau này. Chính vì vậy, sau khi tốt nghiệp phổ thông trung học, sau một thời gian học dự bị đại học, bà được cử đi du học ngành Báo chí quốc tế tại Đại học Quan hệ Quốc tế Matxcơva (MGIMO) (Liên Xô) từ năm 1982.

Sau khi tốt nghiệp năm 1987, bà về nước và được cử vào làm nhân viên Bộ Ngoại giao Việt Nam. Tháng 11 năm 1988, bà chính thức trở thành Chuyên viên của Vụ Thông tin Báo chí, Bộ Ngoại giao. Trong thời gian 3 năm, từ tháng 8 năm 1995 đến tháng 8 năm 1998, bà được cử làm Tùy viên báo chí của Đại sứ quán Việt Nam tại Thái Lan. Sau đó bà lại được rút về làm Chuyên viên Vụ thông tin Báo chí. Tháng 1 năm 2003, bà được thăng làm Phó Vụ trưởng Vụ Thông tin Báo chí.[3]

Tháng 11 năm 2004, bà được cử làm Tham tán của Đại sứ quán Việt Nam Vương quốc Bỉ, Luxembourg và phái đoàn Việt Nam bên cạnh Liên hiệp châu Âu (EU). Tháng 11 năm 2006, bà được thăng lên ngạch Tham tán Công sứ. Đến tháng 11 năm 2007, bà được rút về nước, tiếp tục giữ chức Phó Vụ trưởng Vụ Thông tin Báo chí.[3]

Từ ngày 20 tháng 8 năm 2009, bà được bổ nhiệm giữ chức Vụ trưởng Vụ Thông tin Báo chí và là Người Phát ngôn Bộ Ngoại giao Cộng hòa Xã hội Chủ nghĩa Việt Nam thay ông Lê Dũng (đảm nhận vai trò người đứng đầu Tổng Lãnh sự quán Việt Nam tại Houston, Texas, Hoa Kỳ).[5]

Ngày 12 tháng 9 năm 2011, bà được Thủ tướng Nguyễn Tấn Dũng bổ nhiệm giữ chức Thứ trưởng Bộ Ngoại giao và là nữ Thứ trưởng Ngoại giao đầu tiên của Việt Nam.[6] Bà đã được Chủ tịch nước Cộng hòa Xã hội Chủ nghĩa Việt Nam phong Hàm Đại sứ.[7].

Tháng 11 năm 2014, bà làm Đại sứ Đặc mệnh Toàn quyền, Đại diện thường trực Việt Nam tại Liên Hợp Quốc.[8]

Ngày 9/10/2018, bà được Thủ tướng ký quyết định 1328/QĐ-TTg, bổ nhiệm giữ chức Thứ trưởng Bộ Ngoại giao.

Tháng 12/2018, Ban Bí thư Trung ương Đảng đã điều động bà giữ chức Bí thư Đảng đoàn Liên hiệp các tổ chức hữu nghị Việt Nam - VUFO.

Ngày 10/1/2019, tại Hà Nội, Liên hiệp các tổ chức hữu nghị Việt Nam (VUFO) tổ chức hội nghị Đoàn Chủ tịch khóa V (2013-2018) lần thứ 7. Bà được bầu giữ chức Chủ tịch Liên hiệp với số phiếu tuyệt đối (119/119).[9]